import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
/**
 * 队列+宽搜
 * 429、N叉树的层序遍历
 */
public class Day14 {
    // 429、N叉树的层序遍历
    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> ret = new ArrayList<>();
        if(root == null) {
            return ret;
        }
        // 不为空，就把根节点先入队列
        Queue<Node> queue = new LinkedList<>(); // 存放节点，用于层序遍历，利用先进先出的规则
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size(); // 计算当前队列中节点的个数，也就是当前这一层的节点的个数
            List<Integer> tmp = new ArrayList<>(); // 记录当前这一层的节点的val值
            for(int i = 0;i < size;i++) {
                // 遍历这一层，把val放入tmp中，并且把这一层的每一个节点的孩子节点都放入到队列中，进行下一次的统计
                Node t = queue.poll(); // 出队
                tmp.add(t.val); // 把出队的节点对应的val放入到 这一层的链表中
                for(Node child : t.children) {
                    // 把这个节点的所有孩子节点都放入到队列中
                    queue.add(child);
                }
            }
            ret.add(tmp); // 把tmp的值放入到ret中
        }
        return ret;
    }
}
